import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: XMQ
 * Date: 2022-05-27
 * Time: 15:45
 */
public class Test {

    public static void main(String[] args) {
        String str = "192/142/23/2";
    }
    public static int findNumbers(int[] nums) {
        //暴力解法 leetcode1295
        int count = 0;
        int num = 0;
        for(int i = 0; i < nums.length; i++){
            while((nums[i] ^ 1) != 1){
                nums[i] /= 10;
                num++;
            }
            if(num % 2 ==0){
                count++;
            }
            num = 0;
        }
        return count;
    }
    public static void main2(String[] args) {
        //[580,317,640,957,718,764]
        int[] nums = {555,901,482,1771};
        System.out.println(findNumbers(nums));
    }
    //三数取中
    public static int getMid(int left ,int right){
        int mid = (left+right) >> 1;
        if(left > mid){
            if(mid > right){
                return mid;
            }else if(left < right){
                return left;
            }else{
                return right;
            }
            //left < mid
        }else{
            if(mid < right){
                return mid;
            }else if(left > right){
                return left;
            }else{
                return right;
            }
        }
    }
    public static void swap(int[] nums,int x,int y){
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
    //快排之挖坑法
    public static int part1(int[] nums, int left, int right){
        int index = getMid(left,right);
        swap(nums,left,index);
        int begin = left;
        int end = right;
        int pivot = begin; //坑
        int keyi = nums[begin]; //比较值
        while(begin < end){
            //找小
            while(begin < end && nums[end] >= keyi){
                end--;
            }
            swap(nums,pivot,end);
            pivot = end;
            //找大
            while(begin < end && nums[begin] <= keyi){
                begin++;
            }
            swap(nums,pivot,begin);
            pivot = begin;
        }
        nums[pivot] = keyi;
        return pivot;

    }
    //快排之前后指针法
    public static int part3(int[] nums, int left, int right){
        int index = getMid(left,right);
        swap(nums,left,index);
        int prev = left;
        int cur = left + 1;
        int keyi = left;
        while(cur <= right){
            if(nums[cur] < nums[keyi]
                && ++prev != cur){
                swap(nums,cur,prev);
            }
            cur++;
        }
        swap(nums,keyi,prev);
        return prev;
    }

    public static void quickSort(int[] nums,int left,int right){
        if(left >= right) return;
//        int pivot = part1(nums, left, right);
        int pivot = part3(nums, left, right);
        //[left,pivot-1]pivot[pivot+1,right]
        quickSort1(nums,left,pivot-1);
        quickSort1(nums,pivot+1,right);

    }

    //小区间优化  大可不必
    public static void quickSort1(int[] nums,int left,int right){
        if(left >= right) return;
//        int pivot = part1(nums, left, right);
        int pivot = part3(nums, left, right);
        //[left,pivot-1]pivot[pivot+1,right]
        if(pivot-1-left > 10){
            quickSort1(nums,left,pivot-1);
        }else{
            Arrays.sort(nums);
        }
        if(right-pivot-1 > 10){
            quickSort1(nums,pivot+1,right);
        }else{
            Arrays.sort(nums);
        }
    }
    public static void main1(String[] args) {
        int[] nums = {6,1,2,7,9,3,4,5,10,8};
        quickSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }

}
